package com.cd.algorithm.order.code;

import java.util.Arrays;

/**
 *  {12, 15, 9, 14, 4, 18, 23, 6}
 * 第一轮：拿下标为1的数往下标为1的左侧的数的中间数进行对比，比时左、右、中都是0 第一轮结果  {12, 15, 9, 14, 4, 18, 23, 6}
 * 第二轮：拿下标为2的数往下标为2的左侧的数的中间数进行对比，此时左边界为0，右边界为2-1=1，中位下标为0，第二轮结果{ 9,12, 15, 14, 4, 18, 23, 6}
 * 第三轮：拿下标为3的数往下标小于3的数的中间数进行对比，
 *                      此时左边界为0，右边界为3-1=2，中位下标为（2+0）/2=1,14比12大，则左边界加1，
 *                      此时左边界为1，右边界为2，中位下标为（1+2）/2=1;14比12大，则左边界再加1，
 *                      此时左边界为2，右边界为2，中位数下标也位2，14比15小，则右边界减1，
 *                      此时右边界为1，左边界为2，此时的左边界比右边界大，为错误状态，退出循环，保留左边界下标，将下标为4的数字插下到此下标，之前排好序的数组右移一位
 * 第三轮结果{ 9,12, 14,15, 4, 18, 23, 6}
 * 第四轮：拿下标为4的数往下票小于4的数的中间数进行对比
 *                      此时左边界为0，右边界为4-1=3，中位下标为（3+0）/2=1，4比12小，右边界向减1
 *                      此时左边界为0，右边界为3-1=2，中位下标为（0+2）/2=1，4比12小，右边界再减1
 *                      此时左边界为0，右边界为2-1=1，中位下标为（1+0）/2=0，4比9小，右边界再减1
 *                      此时左边界为0，右边界为1-1=0，中位下票为0，4比9小，右边界再减1
 *                      此时左边界为0，右边界为0-1=-1，此时右边界比左边界小，循环不成立，退出，保留左边界下标，将下标为4的数字插下到此下标，之前排好序的数组右移一位
 * 第四轮结果{ 4,9,12, 14,15,18, 23, 6}
 *
 * 二分插入排序
 * 从第二个下标开始，将要插入的数与前面排好序的中位数进行对比，比其小，则右边界下标左移，比其大，则左边界下标右移，不断缩小边界，至到找到左右边界重合的下标，即为该数的要插入的位置
 * 即该位置左侧比其小，右侧比其大，
 * 遍历该数组其他数字，重复上面操作
 */
public class BinaryInsertionSort {

    public static void main(String[] args) {
//        int[] arr = {12, 15, 9, 14, 4, 18, 23, 6};
        int[] arr = {40,30,50,20};
        System.out.println("Original array:" + Arrays.toString(arr));

//        binaryInsertionSort(arr);
        myTestCode(arr);
        System.out.println("\nSorted array:" + Arrays.toString(arr));
    }

    public static void myTestCode(int[] a) {
        //{40,30,50,20}
        //第一轮： key = 30,left=0,right=0,i=1    如果 0《=0  mid = 0 如果 40《=40 left=1   ,0 >=1条件不成立。。不进循环进行元素右移
        //第二轮： i=2,key=50,
        for (int i = 1; i < a.length; i++) {
            //从最左侧开始为已排好序的左边蜀
            int left = 0 ;
            // 右侧边界为即将要进行对比的该数的左侧，所以减1
            int right = i-1;
            //要与已排好序的一部分进行比较排序的数
            int temp = a[i];
            while (left <= right) {
                //已排好序的中位数  例如 0 8 中位数4
                int mid = (left+right)/2;
                //已排好序的数组的中位数小于等于上面要插入的数的话，则右边界向右移，然后下次再对比的时候就会对比0  3 的中位数
                if(a[mid] <= temp){
                    right = mid - 1;
                }else {
                    left = mid + 1;
                }
            }
            // 将array[i]及之后的元素右移一位，腾出位置给key
            //现在要插入的这个数的前面的数都往右移一位，
            for (int j = i - 1; j >= left; j--) {
                a[j + 1] = a[j];
            }
            //左边界即是这个要插入的数的位置
            a[left] = temp;
        }
    }

    public static void binaryInsertionSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int key = array[i];
            int left = 0;
            int right = i - 1;

            // 使用二分查找找到key应该插入的位置
            while (left <= right) {
                int mid = (left + right) / 2;
                if (key < array[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }

            // 将array[i]及之后的元素右移一位，腾出位置给key
            for (int j = i - 1; j >= left; j--) {
                array[j + 1] = array[j];
            }

            // 将key插入到正确的位置
            array[left] = key;
        }
    }
}
